package Lee_code;

import com.sun.org.apache.xpath.internal.WhitespaceStrippingElementMatcher;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

/**
 * @author blh
 * @date 2024年07月17日 8:31
 */
public class Lee_662_717 {
    public int widthOfBinaryTree(TreeNode root) {
        // 给节点编序号, 第n行第i个节点是
        // 进行层序遍历

        Deque<TreeNode> deque = new ArrayDeque<>();
        root.val = 1;
        deque.add(root);
        Long maxCount = 1L;
        while (!deque.isEmpty()) {
            int size = deque.size();
            Long min = Long.MAX_VALUE;
            Long max = 1L;
            for (int i = 0; i < size; i++) {
                TreeNode temp = deque.poll();
                if (temp.left != null) {
                    temp.left.val = 2* temp.val;
                    deque.offer(temp.left);
                    min = Math.min(min, temp.left.val);
                    max = Math.max(max, temp.left.val);
                }
                if (temp.right != null) {
                    temp.right.val = 2* temp.val + 1;
                    deque.offer(temp.right);
                    min = Math.min(min, temp.right.val);
                    max = Math.max(max, temp.right.val);
                }
            }
            maxCount = Math.max(max-min + 1, maxCount);
        }
        return Math.toIntExact((maxCount));
    }
}
